From 6e53b55d807fffa90baa5402f35dbfb055c73d19 Mon Sep 17 00:00:00 2001
From: Geoffry Song <goffrie@dropbox.com>
Date: Thu, 21 Sep 2017 12:15:49 -0700
Subject: [PATCH] Don't visit the same unit multiple times.

This fixes some accidentally-exponential behaviour we were seeing in our
fairly large workspace. It brings a no-op cargo run from about 10
seconds to 0.3 seconds on my machine.

Also changes an association list to a hashmap because that was showing
up in profiles too.
---
 src/cargo/core/package.rs            |  7 +++----
 src/cargo/ops/cargo_rustc/context.rs | 11 ++++++++---
 2 files changed, 11 insertions(+), 7 deletions(-)

diff --git a/src/cargo/core/package.rs b/src/cargo/core/package.rs
index 493c2a248..9d16b1f28 100644
--- a/src/cargo/core/package.rs
+++ b/src/cargo/core/package.rs
@@ -162,7 +162,7 @@ impl hash::Hash for Package {
 }
 
 pub struct PackageSet<'cfg> {
-    packages: Vec<(PackageId, LazyCell<Package>)>,
+    packages: HashMap<PackageId, LazyCell<Package>>,
     sources: RefCell<SourceMap<'cfg>>,
 }
 
@@ -178,14 +178,13 @@ impl<'cfg> PackageSet<'cfg> {
     }
 
     pub fn package_ids<'a>(&'a self) -> Box<Iterator<Item=&'a PackageId> + 'a> {
-        Box::new(self.packages.iter().map(|&(ref p, _)| p))
+        Box::new(self.packages.keys())
     }
 
     pub fn get(&self, id: &PackageId) -> CargoResult<&Package> {
-        let slot = self.packages.iter().find(|p| p.0 == *id).ok_or_else(|| {
+        let slot = self.packages.get(id).ok_or_else(|| {
             internal(format!("couldn't find `{}` in package set", id))
         })?;
-        let slot = &slot.1;
         if let Some(pkg) = slot.borrow() {
             return Ok(pkg)
         }
diff --git a/src/cargo/ops/cargo_rustc/context.rs b/src/cargo/ops/cargo_rustc/context.rs
index 56bbe9470..cec2e39b0 100755
--- a/src/cargo/ops/cargo_rustc/context.rs
+++ b/src/cargo/ops/cargo_rustc/context.rs
@@ -194,13 +194,14 @@ impl<'a, 'cfg> Context<'a, 'cfg> {
     /// all the units mentioned in `units`.
     pub fn probe_target_info(&mut self, units: &[Unit<'a>]) -> CargoResult<()> {
         let mut crate_types = BTreeSet::new();
+        let mut visited_units = HashSet::new();
         // pre-fill with `bin` for learning about tests (nothing may be
         // explicitly `bin`) as well as `rlib` as it's the coalesced version of
         // `lib` in the compiler and we're not sure which we'll see.
         crate_types.insert("bin".to_string());
         crate_types.insert("rlib".to_string());
         for unit in units {
-            self.visit_crate_type(unit, &mut crate_types)?;
+            self.visit_crate_type(unit, &mut crate_types, &mut visited_units)?;
         }
         debug!("probe_target_info: crate_types={:?}", crate_types);
         self.probe_target_info_kind(&crate_types, Kind::Target)?;
@@ -214,8 +215,12 @@ impl<'a, 'cfg> Context<'a, 'cfg> {
 
     fn visit_crate_type(&self,
                         unit: &Unit<'a>,
-                        crate_types: &mut BTreeSet<String>)
+                        crate_types: &mut BTreeSet<String>,
+                        visited_units: &mut HashSet<Unit<'a>>)
                         -> CargoResult<()> {
+        if !visited_units.insert(*unit) {
+            return Ok(());
+        }
         for target in unit.pkg.manifest().targets() {
             crate_types.extend(target.rustc_crate_types().iter().map(|s| {
                 if *s == "lib" {
@@ -226,7 +231,7 @@ impl<'a, 'cfg> Context<'a, 'cfg> {
             }));
         }
         for dep in self.dep_targets(&unit)? {
-            self.visit_crate_type(&dep, crate_types)?;
+            self.visit_crate_type(&dep, crate_types, visited_units)?;
         }
         Ok(())
     }
-- 
2.30.2